class Solution {


    public Node copyRandomList(Node head) {
        //1. 创建复制节点,copy random 关系,去除原有节点
        return copy(head);
    }

    public Node copy(Node head) {


        if (head == null) {
            return null;
        }

        Node currentNode = head;
        Node newCloneNode = null;
        while (true) {
            //复制自己
            newCloneNode = new Node(currentNode.val, currentNode.next, currentNode.random);

            currentNode.next = newCloneNode;

            currentNode = newCloneNode.next;

            if (currentNode.next == null) {
                break;
            }
        }

        //再遍历一次，更新random节点
        currentNode = head.next;
        while (true) {
            if (currentNode.random != null) {
                currentNode.random = currentNode.random.next;
            }

            if (currentNode.next.next == null) {
                break;
            }

            currentNode = currentNode.next.next;
        }

        //节点拆除
        currentNode = head;
        Node currentCopyNode = head.next;

        Node result = head.next;
        while (true) {
            //先处理原节点
            currentNode.next = currentCopyNode.next;

            currentCopyNode.next = currentCopyNode.next.next;


            currentNode = currentNode.next;
            currentCopyNode = currentCopyNode.next;

            if (currentNode == null || currentCopyNode == null) {
                break;
            }
        }

        return result;
    }
}

class Node {
    public int val;
    public Node next;
    public Node random;

    public Node() {}

    public Node(int _val,Node _next,Node _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};